Go
围棋起源于古代中国，是世界上最古老的棋类运动之一。在宋代的《梦溪笔谈》中探讨了围棋的局数变化数目，作者沈括称“大约连书万字四十三个，即是局之大数”，意思是说变化数目要写43个万字。根据围棋规则，没有气的子不能存活，扣除这些状态后的合法状态约有 \(2.08×10^{170}\) 种。Robertson 与 Munro 在1978年证得围棋是一种 PSPACE-hard 的问题，其必胜法之记忆计算量在\(10^{600}\) 以上，这远远超过可观测宇宙的原子总数 \(10^{75}\)，可见围棋对传统的搜索方法是非常有挑战的。
AlphaGo
AlphaGo是第一个打败人类冠军的电脑程序。
网络结构
它由两个卷积神经网络组成，分别是策略网络和价值网络。
策略网络 P 推荐下一步怎么走；它的输入就是棋盘的矩阵：白棋和黑棋的位置。这个网络由许多卷积层组成，逐渐学习围棋知识，最终输出行动（action）的概率分布，来推荐下一步怎么走。
价值网络也由卷积神经网络组成，它是用来预测这盘棋的胜者。它的输入也是棋盘矩阵，输出是一个属于 \([-1, +1]\) 的标量，-1代表AlphaGo一定会输，+1代表一定会赢。
训练流程
首先是监督学习，让策略网络学习人类专家的数据集：每一个棋面都有一个标签，对应人类专家的下法，让AlphaGo首先学习专家的走法。然后使用策略网络进行自我博弈，由于每局都会产生胜者，用这些数据来训练价值网络。
搜索算法
使用策略网络减少搜索宽度，只考虑网络推荐的下法。
还可以使用价值网络来降低搜索树的深度，可以把搜索子树替换为一个值来表明这个局面赢的概率。
不过实际上还是用的蒙特卡洛搜索树。它分为三步：
选择
首先从树根向下遍历，每次选择置信度最高的走法，直到叶节点。置信度是由每个节点中存储的 Q-value 和策略网络给的先验概率 P 组成。
扩展和评估
到了叶节点之后就要扩展这颗树，用策略网络和价值网络分别评估当前局面，把概率最大的节点加入搜索树。
回溯
把新加入节点的价值 v 回溯到路径上的每一个节点的 Q-value 上。
这就是初始版本的AlphaGo，这个版本赢了世界冠军李世石。
AlphaGo Zero
AlphaGo Zero 除了围棋规则本身以外完全移除了人类的围棋知识，它与AlphaGo的主要区别如下：
- 无人类数据
- 完全从自我博弈中学习
- 无手动编码的特征
- 输入只是棋盘本身
- 单一的神经网络
- 策略网络和价值网络合二为一，并且结构改进为ResNet
- 输出部分分为两头，分别输出 policy 和 value
- 更简单的搜索
- 更简单的MCTS，无随机的快速走子，只用神经网络进行评估
增强学习算法
目标：使用高质量（really really high quality）数据来训练神经网络，而最好的数据来源就是AlphaGo自我博弈。
所以流程就是这样的：
- 输入当前的棋局，使用当前的神经网络来指导进行蒙特卡洛搜索，然后下搜索出的那步棋，接着输入后面的棋局、搜索….直到一盘棋结束。
- 下一步就是训练神经网络，使用之前自我对局的数据，训练策略的数据的特征就是任一棋局，标签就是蒙特卡洛搜索的结果，即策略更贴近于AlphaGo实际下的策略（MCTS的搜索结果）
- 与此同时，使用每盘对局的胜者训练价值网络部分。
- 最后，经过训练的神经网络又可以继续进行自我博弈，产生更高质量的数据，然后用这个数据继续训练…. 循环往复，循环的关键在于，经过每个循环，我们都会得到更强的棋手（神经网络），所以继续会得到更高质量的数据。最后就产生了非常强的棋手。
这个算法可以被看作是增强学习里的策略迭代（Policy Iteration）算法：
- Search-Based Policy Improvement （策略增强）
- 用当前的网络进行MCTS
- MCTS搜索出来的结果 > 神经网络直接选择的结果（因为搜索的结果结合了前瞻）
- Search-Based Policy Evaluation （策略评估）
- 使用搜索算法和神经网络进行自我博弈
- 评估改进后的策略
学习曲线
实力
AlphaZero
AlphaZero使用同一种算法学习三种不同的棋类，并都取得了超人的水平。
棋类AI研究情况总结
- 在AI的历史上很早就开始研究棋类，如图灵、香农、冯诺伊曼等
- 专一系统曾在国际象棋上成功过
- 深蓝在1997年击败卡氏
- 现在的象棋程序人类已无法击败
- 将棋（日本象棋）比国际象棋更难
- 更大的棋盘和行动空间
- 只有最近的程序才达到了龙王的水平
- 最前沿的引擎都是根据 alpha-beta 搜索
- 人类大师手工优化的评估函数
- 搜索域针对不同棋类疯狂优化
由上图可见围棋与将棋和象棋还是有很大不同的，但是AlphaZero的主要算法和AlphaGo Zero一样，都是自我博弈的增强学习，只是把一些只针对围棋的细节去掉了（比如通过旋转进行数据增强，因为围棋是对称的）和输入输出维度进行了改变。
它的学习曲线如下，均达到了顶尖水平：
AlphaZero and ExIt
Expert Iteration（ExIt）是一种模仿学习（Imitation Learning, IL）算法，普通的 IL 算法中，徒弟模仿专家的策略只能提高自己的策略，专家是不会有任何提高的，而 ExIt 算法就是想让师傅教徒弟的时候自己也有提高。
ExIt 算法 师傅根据徒弟的策略进行前向搜索（例如MCTS，alpha-beta，贪心搜索等），得出比徒弟更好的策略，然后徒弟再学习师傅的策略，如此循环，随着徒弟的增强，师傅也会越来越强。
可见，AlphaZero也属于 ExIt 算法，师傅为 MCTS，徒弟就是神经网络。
Summary
现在棋类人工智能算法的发展趋势是越来越泛化，趋向于多功能。从 AlphaGo 的学习人类专家的棋谱到 AlphaGo Zero 的从零开始无需人类知识的自我博弈学习再到 AlphaZero 的同一算法适应不同棋类并且都取得超人水平。可见人工智能越来越向通用智能发展，虽然长路漫漫，现在的算法远不够泛化，但是很多东西，比如神经网络结构都是可以用到不同领域的。AlphaGo 系列的作者之一 David Silver 曾说:“每次你专门化一些东西都会伤害你的泛化能力” (Every time you specialize something you hurt your generalization ability.)。事实也的确如此，AlphaGo 系列架构越来越简单，而其性能和泛化能力却越来越强大。